翻訳と辞書 Words near each other ・ Determinism ・ Determinism (disambiguation) ・ Deterministic acyclic finite state automaton ・ Deterministic algorithm ・ Deterministic automaton ・ Deterministic context-free grammar ・ Deterministic context-free language ・ Deterministic encryption ・ Deterministic finite automaton ・ Deterministic garbage collector ・ Deterministic global optimization ・ Deterministic memory ・ Deterministic noise ・ Deterministic Parallel Java ・ Deterministic parsing ・ Deterministic pushdown automaton ・ Deterministic routing ・ Deterministic scale-free network ・ Deterministic simulation ・ Deterministic system ・ Deterministic system (philosophy) ・ Detern ・ Deterrence ・ Deterrence (film) ・ Deterrence (legal) ・ Deterrence (psychology) ・ Deterrence theory ・ Deterring Democracy ・ Deterritorial Support Group ・ Deterritorialization Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Deterministic pushdown automaton ： ウィキペディア英語版 Deterministic pushdown automaton In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton . The DPDA accepts the deterministic context-free languages, a proper subset of context-free languages. Machine transitions are based on the current state and input symbol, and also the current topmost symbol of the stack. Symbols lower in the stack are not visible and have no immediate effect. Machine actions include pushing, popping, or replacing the stack top. A deterministic pushdown automaton has at most one legal transition for the same combination of input symbol, state, and top stack symbol. This is where it differs from the nondeterministic pushdown automaton. == Formal definition == A (not necessarily deterministic) PDA ''M'' can be defined as a 7-tuple: :$M=(Q\backslash ,,\; \backslash Sigma\backslash ,,\; \backslash Gamma\backslash ,,\; q\_0\backslash ,,\; Z\_0\backslash ,,\; A\backslash ,,\; \backslash delta\backslash ,)$ where *$Q\backslash ,$ is a finite set of states *$\backslash Sigma\backslash ,$ is a finite set of input symbols *$\backslash Gamma\backslash ,$ is a finite set of stack symbols *$q\_0\backslash ,\backslash in\; Q\backslash ,$ is the start state *$Z\_0\backslash ,\backslash in\backslash Gamma\backslash ,$ is the starting stack symbol *$A\backslash ,\backslash subseteq\; Q\backslash ,$, where $A$ is the set of accepting states *$\backslash delta\backslash ,$ is a transition function, where :$\backslash delta\backslash colon(Q\backslash ,\; \backslash times\; (\; \backslash Sigma\backslash ,\; \backslash cup\; \backslash left\; \backslash \; )\; \backslash times\; \backslash Gamma\backslash ,)\; \backslash longrightarrow\; \backslash mathcal(Q\; \backslash times\; \backslash Gamma\; ^)$ : where $$ * is the Kleene star, meaning that $\backslash Gamma^$ is "the set of all finite strings (including the empty string $\backslash varepsilon$) of elements of $\backslash Gamma$", $\backslash varepsilon$ denotes the empty string, and $\backslash mathcal(X)$ is the power set of a set $X$. ''M'' is ''deterministic'' if it satisfies both the following conditions: * For any $q\; \backslash in\; Q,\; a\; \backslash in\; \backslash Sigma\; \backslash cup\; \backslash left\; \backslash ,\; x\; \backslash in\; \backslash Gamma$, the set $\backslash delta(q,a,x)\backslash ,$ has at most one element. *For any $q\; \backslash in\; Q,\; x\; \backslash in\; \backslash Gamma$, if $\backslash delta(q,\; \backslash varepsilon,\; x)\; \backslash not=\; \backslash emptyset\backslash ,$, then $\backslash delta\backslash left(\; q,a,x\; \backslash right)\; =\; \backslash emptyset$ for every $a\; \backslash in\; \backslash Sigma.$ There are two possible acceptance criteria: acceptance by ''empty stack'' and acceptance by ''final state''. The two are not equivalent for the deterministic pushdown automaton (although they are for the non-deterministic pushdown automaton). The languages accepted by ''empty stack'' are the languages that are accepted by ''final state'', as well as have no word in the language that is the prefix of another word in the language. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Deterministic pushdown automaton」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.